"""
41.缺失的第一个正数
https://leetcode-cn.com/problems/first-missing-positive

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例1:
输入：nums = [1,2,0]
输出：3

示例2:
输入：nums = [3,4,-1,1]
输出：2

提示:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
"""
class Solution:
  """
  此题目的难点在于如何做到 O(n) 的时间复杂度(注定了不可能对数据进行排序(不管是全排序，还是堆排序),其时间复杂度至少为 O(n log(n)))，与 O(1) 的空间复杂度(无法创建一个新数组结构以容纳原始数据的全部或一部分)
  
  可以如下理解:
    fistMissingPositive(nums) == min(range(1, len(nums) + 2) - nums)
  
  设 hash 函数 f(n) = nums[n] - 1
  这样，我们只需要将 range(0, len(nums)) 以 f(n) 散列在 一个长度为 len(nums) 的数组 x 中
  如果 x 有空位，则为的空位的最小索引，如果没有空位，则为 len(nums) + 1

  这样的算法，时间复杂度为 O(n)，空间复杂度也为 O(n)

  我可们通过复用 nums 的空间(即原地哈希)，来使 空间复杂度降为 O(1)：
    1. 遍历 nums，将所有为负数或0的元素改为 len(nums) + 1
    2. 遍历 nums，如果元素 e 使得 | e | <= len(nums)，则将 nums[| e | - 1] = -1 * | nums[| e | - 1] |
    3. 找出 nums 中值为正数的最小索引 + 1 作为结果，如果没有，则结果为 len(nums) + 1
  """
  def firstMissingPositive(self, nums: list[int]) -> int:
    n = len(nums)

    # 1
    for i in range(n):
      if nums[i] <= 0:
        nums[i] = n + 1
    
    # 2
    for i in range(n):
      v = nums[i]
      if v < 0:
        v = -1 * v
      if v <= n:
        x = nums[v - 1]
        if x > 0:
          nums[v - 1] = -1 * x

    # 3
    for i in range(n):
      if nums[i] > 0:
        return i + 1
    
    return n + 1
    
        